The present invention relates to a method of and an apparatus for generating internal crypto-keys which are used as initial values to be set in feedback registers of an pseudo-random-sequence generator for generating pseudo-random-numbers to be XORed (added according to eXclusive OR logic) onto a data sequence recorded in a recording medium or to be transmitted in a communication system, for preventing a third party from tapping the data sequence without permission.
Cryptography called secret-key-cryptography can be classified into two types, cryptography called block ciphers and cryptography called stream ciphers. In the former cryptography, data of a fixed length, 64 bits, for example, called the plain text is transformed into a data block called the cipher text according to a certain transformation algorithm. On the other hand, a sequence of pseudo-random-numbers called the key-stream is XORed onto a data stream called the plain text stream to be converted into a cipher-stream.
As a method of generating a pseudo-random-sequence which is cryptographically secure, there is known a method making use of a one-way function such as a public-key-cryptograph function. Here, the one-way function means a function f(x) which can be easily calculated from a variable x, but it is hardly possible to estimate the variable x from an output of the function f(x).
FIG. 5 is a block diagram illustrating a configuration example of a conventional pseudo-random-sequence generator which generates the cryptographically secure pseudo-random-sequence.
Referring to FIG. 5, an external key-data of n-bits is supplied to a first input terminal 405. A one-way function circuit 101 outputs an n-bit conversion result by processing n-bit output of a selector 201 with a certain one-way function (such as a public key function) according to a certain conversion parameter (such as a public key) supplied to a second input terminal 104. The LSB (Least Significant Bit) of the conversion result is output from an output terminal 508 as a bit of the pseudo-random-sequence.
With each clock pulse CLK supplied from a clock terminal 210, a register 202 outputs registered n-bit data to the selector 201 and newly registers the n-bit conversion result of the one-way function circuit 101.
Only when the clock pulse CLK is supplied for the first to the register 202, a selection signal SEL supplied to the selector 210 through a selection terminal 211 is set at logic `0` for controling the selector 201 to output the external key-data supplied from the first input terminal 405 to the one-way function circuit 101, and afterwards the selection signal SEL is turned to logic `1` so that the selector is controlled to select the output of the register 202 to be fed-back to the one-way function circuit 101.
Thus, the pseudo-random-sequence is output bit-by-bit from the output terminal 508 in synchronization with the clock pulse CLK.
The pseudo-random-sequence generator of FIG. 5 is known to be cryptographically secure. However, calculation of the one-way function takes comparatively long time.
Therefore, a pseudo-random-sequence generator consisting of combination of several linear feedback-sift-registers or nonlinear feedback-shift-registers is generally used for generating the key-stream of the stream cipher, when a high speed is required, having such configuration as illustrated in a block diagram of FIG. 6.
In the pseudo-random-sequence generator of FIG. 6, there are comprised linear feedback-sift-registers or nonlinear feedback-shift-registers (hereinafter generically called the feedback-shift-registers) S.sub.1 to S.sub.n. To each of the feedback-shift-registers, working as a sub-generator, an internal key K.sub.1 to K.sub.n is set initially. At each clock, each of the feedback-shift-resisters is shifted by one bit outputting its LSB to a combination function F, and its MSB (Most Significant Bit) is generated according to a certain feedback function from its registered bit sequence. The combination function F generates a key-stream bit by bit according to a certain combination function from outputs of the feedback-shift-registers S.sub.1 to S.sub.n.
However, the key-stream generated making use of feedback-shift-registers, such as illustrated in FIG. 6, may sometimes be broken by a deciphering method called correlation attacks. So, various kinds of devices has been studied, whereof some examples are described in "Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C," by Bruce Schneier, published by John Wiley & Sons, Inc., 1996, and as to the correlation attacks, there is an explanation in "Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications" by T. Siegenthaler, IEEE Transactions on Information Theory, Vol. IT-30, No. 5, 1984, for example. However, description of details of the pseudo-random-sequence generator itself or the correlation attacks is omitted, here.
In any way, to be sufficiently robust against cryptographic analysis such as the correlation attacks, sufficient numbers of sufficiently long-bit feedback-shift-registers should be used for generating the key-stream, which requires numbers of internal keys to be set to the feedback-shift-registors as their initial values.
On the other hand, bit-length of a secret crypto-key is usually limited practically, such as 64 bits, for example. Therefore, it is important for the pseudo-random-sequence generator consisting of feedback-shift-registers how to securely generate numbers of internal keys to be set thereto, from a secret-key given from external (hereinafter called the external key).
As above mentioned, one or some internal keys may be estimated by the correlation attacks. Hence, when the internal keys are generated from a single external key without sufficient care, all the internal keys may be easily estimated based on the broken internal keys.
Cryptographically secure internal keys may be obtained making use of a one-way function in the same way with generating the pseudo-random-sequence itself, by the pseudo-random-sequence generator of FIG. 5, for example. However, a demerit of obtaining the internal keys by way of the one-way function lies in that it takes too long time even for generating the internal keys once at the beginning of a cipher-stream. Because, the pseudo-random-sequence generator cannot but generate the pseudo-random-numbers bit by bit. Therefore, n.times.m clocks should be needed for generating n sets of internal keys of m bits, for example, and the clock frequency cannot be made high because of comparatively long calculation time of the one-way function.